/**
 * 项目名称: Topic_117.cpp
 * 项目路径: study/DataStructure/LeetCode/树/中等
 * 编辑时间: 2024年08月16日15时28分28秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution {
public:
    vector<vector<Node*>>vn;
    vector<Node*>init;
    void pre(Node* root,int study){
        if(root){
            study++;
            if(vn.size()<=study)vn.push_back(init);
            vn[study].push_back(root);
            pre(root->left,study);
            pre(root->right,study);
        }
    }

    Node* connect(Node* root) {
        if(!root)return nullptr;
        vn.push_back(init);
        vn[0].push_back(root);
        pre(root,0);

        for(auto x:vn)cout<<to_string(x.size())<<" ";

        for(int i =0;i<vn.size();i++){
            for(int j = 0;j<vn[i].size()-1;j++){
                vn[i][j]->next = vn[i][j+1];
            }
            vn[i][vn[i].size()-1]->next= nullptr;
        }
        return root;
    }
};